package com.lht.leetcodeDemo;

import com.lht.leetcodeDemo.data.structure.TreeNode;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author Eric
 * @version 1.0
 * @date 2019-12-10
 */
public class PathSumII {

    @Test
    public void test() {
        TreeNode root = new TreeNode(5);
        TreeNode rleft = new TreeNode(4);
        TreeNode rRight = new TreeNode(8);
        root.left = rleft;
        root.right = rRight;

        TreeNode dd = new TreeNode(11);
        rleft.left = dd;

        TreeNode cc = new TreeNode(13);
        TreeNode bb = new TreeNode(4);
        rRight.left = cc;
        rRight.right = bb;

        TreeNode ee = new TreeNode(7);
        TreeNode ff = new TreeNode(2);
        dd.left = ee;
        dd.right = ff;

        TreeNode gg = new TreeNode(5);
        TreeNode g1 = new TreeNode(2);
        bb.left = gg;
        bb.right = g1;

        Solution s = new Solution();
        List<List<Integer>> arr = s.pathSum(root, 0);
        for (List<Integer> a : arr) {
            a.forEach(v -> {
                System.out.print(v);
            });
            System.out.println();
        }
    }

    class Solution {
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            List<List<Integer>> rst = new ArrayList<>();
            if (root == null) {
                return rst;
            }
            List<Integer> path = new ArrayList<>();
            path.add(root.val);
            sum -= root.val;
            if (sum == 0) {
                rst.add(path);
                return rst;
            } else if (sum > 0) {
                path(root.left, sum, rst, path);
                path(root.right, sum, rst, path);
            }
            return rst;
        }

        public void path(TreeNode node, int sum, List<List<Integer>> rst, List<Integer> path) {
            if (node == null) {
                return;
            }
            List<Integer> copyPath = new ArrayList<>();
            path.forEach(v -> copyPath.add(v));
            copyPath.add(node.val);
            sum -= node.val;
            if (sum == 0) {
                rst.add(copyPath);
            } else if (sum > 0) {
                path(node.left, sum, rst, copyPath);
                path(node.right, sum, rst, copyPath);
            }
        }
    }

}
